import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-12
 * Time: 13:45
 */
public class Test {
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/394806482/
    //学习哈希思想
class Solution {
    //题目条件给出了所有的val不相同，所以可以使用哈希
    Map<Integer, TreeNode> parent = new HashMap<>();//根据val记录父节点
    Set<Integer> visted = new HashSet<>();//记录所有的祖先结点的val

    //初始化parent
    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        dfs(root);
        while (p != null) {
            visted.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visted.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
}